Embodiments of the invention are generally directed to techniques for identifying and maintaining dependency relationships between matrix supernodes during matrix factorization. More specifically, embodiments presented herein maintain a list of dependencies for each supernode in a data structure and augment the list as needed when a column is moved from one supernode to another.
A variety of scientific applications require the computation of a vector x which satisfies the matrix equation A*x=b, where A is an n-by-n symmetric matrix and b is an n-by-1 matrix (i.e., a column vector). Often this is required for a sequence of related matrices A in which the values of the matrix change, but the location of non-zero values remains the same for all matrices A in the sequence.
A common method for computing vector x is to factor matrix A into two n-by-n matrices A=L*L′, where L′ denotes the transpose of L. The structure of L makes it easy to compute x by first computing a vector y such that L*y=b, then computing x as the solution of L′*x=y. To improve the computational efficiency of the matrix factorization, systems typically take advantage of the sparse nature of A by storing the matrix data in a “supernodal” data structure, where adjacent columns in the matrix with a similar pattern of rows in which the non-zeros appear are stored in a packed array of floating point numbers called a supernode. Over the course of the factorization, a column may be moved from one supernode to another (referred to as “deferring a column) if doing so may result in less numerical error in the computation. Further, one common operation that occurs during matrix factorization is to perform a sparse matrix multiplication and addition that modifies a supernode S based on the values stored in a supernode T, such that supernode T has a non-zero row corresponding to a column of S. This operation may be referred to as “an external update of S by T” and supernode S may be said to “depend” on supernode T.
One existing approach to determine which supernodes a supernode S depends on is to iterate over all supernodes of the matrix at the beginning of each factorization, and for each supernode T, for each supernode S that depends on T, add T to a data structure that belongs to the supernode S. However, where factorization is required for a series of symmetric matrices A in which the location of non-zeros is the same in each matrix in the series, iterating over all supernodes at the beginning of each factorization adds significant overhead to the factorization.